package com.arithmeticEveryDay.leetCode;

import java.util.Scanner;

/*

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

4
5
11110
11010
11000
00000


4
5
11000
11000
00100
00011

 */

public class Solution200 {

    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    visited[i][j] = true;
                    find1(i, j, grid, visited);
                    count++;
                }
            }
        }
        return count;
    }
    
    private void find1(int i, int j, char[][] grid, boolean[][] visited) {
        int m = grid.length;
        int n = grid[0].length;
        if (i - 1 >= 0) {
            if (grid[i-1][j] == '1' && !visited[i-1][j]) {
                visited[i-1][j] = true;
                find1(i-1, j, grid, visited);
            }
        }
        if (i + 1 < m) {
            if (grid[i+1][j] == '1' && !visited[i+1][j]) {
                visited[i+1][j] = true;
                find1(i+1, j, grid, visited);
            }
        }
        if (j - 1 >= 0) {
            if (grid[i][j-1] == '1' && !visited[i][j-1]) {
                visited[i][j-1] = true;
                find1(i, j-1, grid, visited);
            }
        }
        if (j + 1 < n) {
            if (grid[i][j+1] == '1' && !visited[i][j+1]) {
                visited[i][j+1] = true;
                find1(i, j+1, grid, visited);
            }
        }
        
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        char[][] grid = new char[m][n];
        for (int i = 0; i < m; i++) {
            grid[i] = scan.next().toCharArray();
        }
        Solution200 s = new Solution200();
        System.out.println(s.numIslands(grid));
    }

}
